/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-10-13
 * Time: 20:01
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 全排列 深度优先遍历
 */
public class Main4 {

    public static void main(String[] args) {
        int []nums = {1,2,3,4,5,6};
        List<List<Integer>> res = permute(nums);
        System.out.println(res.size());
    }
    public static List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>(); //存放结果
        if( len ==0) {             //当数组长度为0,返回空
            return res;
        }

        Stack<Integer> path = new Stack<>(); //存放已经用过的数字
        boolean[] used = new boolean[len];   //标记数组,初始化为false ,用来标记当前这个数是否被用使用过
        dfs(nums, len, 0, path, used, res); //深度优先遍历查找 叶子节点
        return  res;
    }

    private static void dfs(int[] nums, int len, int depth, Stack<Integer> path, boolean[] used, List<List<Integer>> res) {
        //递归终止条件,当 深度等于 数组长度时, 说明所有数字都已经用到了,递归终止
        if(depth == len) {
            res.add( new ArrayList<>(path));  //path是一个引用,指向的是一个栈, 直接存放到res中会变成空, 需要 new成一个顺序表,再存进去
            return ;
        }
        //循环产生新的分支
        for( int i=0;i<len; i++) {
            if( used[i]) {    //为真,说明当前数已经被用过了,直接返回判断部分,
                continue;
            }
            path.push(nums[i]); //当前数入栈
            used[i] = true;     //改变当前数的标记,说明该数已用过
            dfs(nums, len, depth+1, path, used, res); //进一层遍历
            //进行回溯, 取消递归之前的操作
            path.pop();
            used[i] = false;
        }
    }
}
